package com.xyhuo.leetcode.december;

import java.util.HashMap;
import java.util.Map;

/**
 * 找出叠涂元素
 * https://leetcode.cn/problems/first-completely-painted-row-or-column/
 *
 * @time 2023/12/1
 */
public class FirstCompleteIndex {

//    public static void main(String[] args) {
//        int[] arr = {1, 4, 5, 2, 6, 3};
//        int[][] mat = {{4, 3, 5}, {1, 2, 6}};
//        FirstCompleteIndex firstCompleteIndex = new FirstCompleteIndex();
//        firstCompleteIndex.firstCompleteIndex(arr, mat);
//    }

    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[2][Math.max(m, n)];
        Map<Integer, MatrixIndex> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                MatrixIndex index = new MatrixIndex(i, j);
                map.put(mat[i][j], index);
            }
        }
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            MatrixIndex index = map.get(arr[i]);
            int m1 = dp[0][index.i] + 1;
            if (m1 == n) {
                return i;
            }
            int n1 = dp[1][index.j] + 1;
            if (n1 == m) {
                return i;
            }

            dp[0][index.i] += 1;
            dp[1][index.j] += 1;
        }
        return -1;
    }

    class MatrixIndex {
        private int i;
        private int j;

        MatrixIndex(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}
